package com.xzz.uf;

import java.util.Arrays;

/**
 * @author: hhz
 * @create: 2022-01-24 16:28
 * 684. 冗余连接
 **/
public class FindRedundantConnection {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findRedundantConnection(new int[][]{{1, 2}, {1, 3}, {2, 3}})));
        System.out.println(Arrays.toString(findRedundantConnection(new int[][]{{1, 2}, {2, 3}, {3, 4},{1,4},{1,5}})));
    }
    public static int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UF uf = new UF(n);
        for (int[] edge : edges) {
            if(!uf.connected(edge[0]-1,edge[1]-1)){
                uf.union(edge[0]-1,edge[1]-1);
            }else {
                return edge;
            }
        }
        return new int[]{-1,-1};
    }
}
